#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cstring>
#define endl "\n"
using namespace std;
int lie[20];
const int N=20;
int n,k=0;
bool a[N],a1[2*N],a2[2*N];
bool panduan(int x,int y)
{
    if(!a[y]&&!a1[x-y+n]&&!a2[x+y])
    {
        return true;
    }
        return false;
}
void dfs(int x)
{
    if (x >=n) {
    	if(k<3)
    	{
    		for(int i=0;i<n;i++)
    		{
    			cout<<lie[i]+1<<" ";
			}
			cout<<endl;
		}
        k++;
        return;
    }

    for(int y=0;y<n;y++ )
    {
        if(panduan(x,y))
        {
        	lie[x]=y;
            a[y]=a1[x-y+n]=a2[x+y]=true;
            dfs(x+1);
            a[y]=a1[x-y+n]=a2[x+y]=false;
        }
    }

}
int main()
{
    cin>>n;
    dfs(0);
    cout<<k<<endl;
    return 0;
}
